package medium;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2021/10/23 12:34
 */
public class No46_全排列 {
    public static void main(String[] args) {
        Solution46 solution46 = new Solution46();
        int[] nums = new int[]{1, 2, 3, 4};
        List<List<Integer>> permute = solution46.permute(nums);
        System.out.println(permute);
    }
}

class Solution46 {
    public List<List<Integer>> permute(int[] nums) {
        //动态规划
        //dp
        List<List<Integer>>[] dp = new ArrayList[nums.length];
        //dp初始化
        for (int i = 0; i < dp.length; i++) {
            dp[i] = new ArrayList<>();
        }
        
        //假如nums:1234,做分析 dp[0] = [[1]]
        List<Integer> init = new ArrayList<>();
        init.add(nums[0]);//[1]
        //List<List<Integer>> init0 = new ArrayList<>();
        //init0.add(init);
        dp[0].add(init);
        for (int i = 1; i < dp.length; i++) {
            //已知dp[2] = [[12][21]]
            //计算dp[3]
            //数字进来
            int numData = nums[i];
            //先获取上一级的list
            List<List<Integer>> preList = dp[i - 1];//[12][21]
            //元素遍历,获取一个一个List<Integer>
            for (int j = 0; j < preList.size(); j++) {
                List<Integer> data = preList.get(j);//[12]
                //[12]->[312][132][123]
                //索引0-长度(包含)遍历
                for (int k = 0; k <= data.size(); k++) {
                    //每个索引位置插入
                    //值传递问题
                    List<Integer> kData = new ArrayList<>(data);
                    kData.add(k, numData);//[312]
                    //加入i位置
                    dp[i].add(kData);
                }
            }
        }
        return dp[nums.length - 1];
    }
}



    ////已经递归过的元素
    //Set<Integer> overSet = new HashSet<>();
    //List<List<Integer>> res = new ArrayList<>();
    //public List<List<Integer>> permute(int[] nums) {
    //    //123   -> 123,132,213,231,312,321->    111,211,112 xx
    //    //123456 -> .......
    //    //狂暴的递归
    //    //No39.组合总和
    //    List<Integer> data = new ArrayList<>();
    //    permute(nums, data);
    //    return res;
    //}
    //
    ////data:递归过程中维护的元素
    //public void permute(int[] nums, List<Integer> data) {
    //    //递归终止条件
    //    if (overSet.size() == nums.length) {
    //        //注意值传递问题
    //        List<Integer> dataCopy = new ArrayList<>(data);
    //        res.add(dataCopy);
    //        return;
    //    }
    //    
    //    //每一轮循环都要递归
    //    for (int i = 0; i < nums.length; i++) {
    //        int yuansu = nums[i];
    //        //如果有,不行,没有才可!!
    //        if (overSet.add(yuansu)) {
    //            data.add(yuansu);
    //            permute(nums, data);
    //            //回溯
    //            data.remove(data.size() - 1);
    //            overSet.remove(yuansu);
    //        }
    //    }
    //}










